1635E - Cars - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define mp make_pair
#define F first
#define S second

int n, m;
vector<pair<pii, bool>> qs;  // true = irrelevant; false = destined
vector<vector<int>> adj;     // to check if bipartite
vector<int> comp;            // 0 = unvisited; 1 = left; 2 = right
vector<vector<int>> dir;     // for topsort
vector<int> indeg;           // for topsort
vector<int> pos;             // answer

bool dfs(int p) {
  for (int q : adj[p]) {
    if (comp[q] == 0) {
      comp[q] = 3 - comp[p];
      if (!dfs(q)) return false;
    }
    if (comp[q] == comp[p]) {
      return false;
    }
  }
  return true;
}

void compute() {
  for (auto q : qs) {
    adj[q.F.F].push_back(q.F.S);
    adj[q.F.S].push_back(q.F.F);
  }

  comp.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    if (comp[i] != 0) continue;

    comp[i] = 1;
    if (!dfs(i)) {
      cout << "NO\n";
      return;
    }
  }

  dir.resize(n + 1);
  indeg.resize(n + 1);
  // it is now known that the graph is bipartite
  for (auto q : qs) {
    if (comp[q.F.S] == 1) swap(q.F.F, q.F.S);
    if (q.S) {
      dir[q.F.F].push_back(q.F.S);
      indeg[q.F.S]++;
    } else {
      dir[q.F.S].push_back(q.F.F);
      indeg[q.F.F]++;
    }
  }

  // for (int i = 1; i <= n; i++) {
  //   cout << i << " : ";
  //   for (int q : dir[i]) cout << q << " ";
  //   cout << "\n";
  // }

  queue<int> q;
  for (int i = 1; i <= n; i++) {
    if (indeg[i] == 0) {
      q.push(i);
    }
  }
  vector<int> order;
  while (!q.empty()) {
    int curr = q.front();
    // cout << curr << "\n";
    q.pop();
    order.push_back(curr);
    for (int next : dir[curr]) {
      indeg[next]--;
      if (indeg[next] == 0) {
        q.push(next);
      }
    }
  }

  if ((int)order.size() != n) {  // loop exists, bad
    cout << "NO\n";
    return;
  }

  pos.resize(n + 1);
  for (int i = 0; i < n; i++) pos[order[i]] = i;

  cout << "YES\n";
  for (int i = 1; i <= n; i++) {
    cout << (comp[i] == 1 ? "L" : "R") << " " << pos[i] << "\n";
  }
}

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

  cin >> n >> m;
  adj.resize(n + 1);

  while (m--) {
    int t, a, b;
    cin >> t >> a >> b;
    qs.push_back(mp(mp(a, b), t == 1));
  }

  compute();

  return 0;
}